package com.tgy.leetcode.backtracking;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-11-21 13:36
 * https://leetcode-cn.com/problems/combination-sum-ii/
 *
 *
 */
public class _40_组合总和_II {

    private List<List<Integer>> lists;
    private int[] candidates;

    private int target;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {


        if (Objects.isNull(candidates) || candidates.length == 0 || target <= 0) {

            return new LinkedList<>();
        }

        this.target = target;
        this.candidates = candidates;
        Arrays.sort(candidates);

        System.out.println(Arrays.toString(candidates) + "\n");

        if (this.target < candidates[0]) {

            return new LinkedList<>();
        }
        lists = new LinkedList<>();
        sum(0,0, new LinkedList<>());

        return lists;
    }

    private void sum(int index, int sum, LinkedList<Integer> combinations) {

        if (index >= this.candidates.length) {

            return;
        }

        int tmpSum;

        Integer beforeSelect = null;
        // 广度
        for (int i = index; i < this.candidates.length ; i++) {



            tmpSum = sum + this.candidates[i];

            if (tmpSum > this.target) {

                break;
            }

            // i组合是 i-1组合的子集合
            if (i > index && this.candidates[i - 1] == this.candidates[i]) {

                continue;
            }

            combinations.add(this.candidates[i]);

            if (tmpSum < this.target) {

                // 深度
                sum(i+1,tmpSum,combinations);
            }else {


                this.lists.add(new LinkedList<>(combinations));
            }

            combinations.removeLast();
        }

    }
}
